/*-------------------------------------------------------------------------
 *
 * bipartite_match.c
 *	  用于二分图的 Hopcroft-Karp 最大基数算法
 *
 * 该实现基于以下伪代码：
 *
 * https://en.wikipedia.org/w/index.php?title=Hopcroft%E2%80%93Karp_algorithm&oldid=593898016
 *
 * Copyright (c) 2015-2022, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *	  src/backend/lib/bipartite_match.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <limits.h>

#include "lib/bipartite_match.h"
#include "miscadmin.h"

/*
 * 在hk_breadth_search中计算的距离显然从未
 * 超过u_size。由于我们将u_size限制为小于SHRT_MAX，
 * 因此可以使用SHRT_MAX作为作为标记所需的“无穷大”距离。
 */
#define HK_INFINITY  SHRT_MAX

static bool fc_hk_breadth_search(BipartiteMatchState *fc_state);
static bool fc_hk_depth_search(BipartiteMatchState *fc_state, int fc_u);

/*
 * 给定U和V的大小，其中每个索引为1..size，以及一个邻接
 * 列表，执行匹配并返回结果状态。
 */
BipartiteMatchState *
BipartiteMatch(int fc_u_size, int fc_v_size, short **fc_adjacency)
{
	BipartiteMatchState *fc_state = palloc(sizeof(BipartiteMatchState));

	if (fc_u_size < 0 || fc_u_size >= SHRT_MAX ||
		fc_v_size < 0 || fc_v_size >= SHRT_MAX)
		elog(ERROR, "invalid set size for BipartiteMatch");

	fc_state->u_size = fc_u_size;
	fc_state->v_size = fc_v_size;
	fc_state->adjacency = fc_adjacency;
	fc_state->matching = 0;
	fc_state->pair_uv = (short *) palloc0((fc_u_size + 1) * sizeof(short));
	fc_state->pair_vu = (short *) palloc0((fc_v_size + 1) * sizeof(short));
	fc_state->distance = (short *) palloc((fc_u_size + 1) * sizeof(short));
	fc_state->queue = (short *) palloc((fc_u_size + 2) * sizeof(short));

	while (fc_hk_breadth_search(fc_state))
	{
		int			fc_u;

		for (fc_u = 1; fc_u <= fc_u_size; fc_u++)
		{
			if (fc_state->pair_uv[fc_u] == 0)
				if (fc_hk_depth_search(fc_state, fc_u))
					fc_state->matching++;
		}

		CHECK_FOR_INTERRUPTS(); /* 以防万一 */
	}

	return fc_state;
}

/*
 * 释放由BipartiteMatch返回的状态，除了原始邻接
 * 列表，该列表由调用者拥有。这仅释放内存，因此是可选的。
 */
void BipartiteMatchFree(BipartiteMatchState *fc_state)
{
	/* 邻接矩阵被视为由调用者拥有 */
	pfree(fc_state->pair_uv);
	pfree(fc_state->pair_vu);
	pfree(fc_state->distance);
	pfree(fc_state->queue);
	pfree(fc_state);
}

/*
 * 执行H-K匹配的广度优先搜索步骤。
 * 如果成功，则返回true。
 */
static bool fc_hk_breadth_search(BipartiteMatchState *fc_state)
{
	int			fc_usize = fc_state->u_size;
	short	   *fc_queue = fc_state->queue;
	short	   *fc_distance = fc_state->distance;
	int			fc_qhead = 0;		/* 我们从不将任何节点入队多于一次 */
	int			fc_qtail = 0;		/* 因此不必担心包裹 */
	int			fc_u;

	fc_distance[0] = HK_INFINITY;

	for (fc_u = 1; fc_u <= fc_usize; fc_u++)
	{
		if (fc_state->pair_uv[fc_u] == 0)
		{
			fc_distance[fc_u] = 0;
			fc_queue[fc_qhead++] = fc_u;
		}
		else
			fc_distance[fc_u] = HK_INFINITY;
	}

	while (fc_qtail < fc_qhead)
	{
		fc_u = fc_queue[fc_qtail++];

		if (fc_distance[fc_u] < fc_distance[0])
		{
			short	   *fc_u_adj = fc_state->adjacency[fc_u];
			int			fc_i = fc_u_adj ? fc_u_adj[0] : 0;

			for (; fc_i > 0; fc_i--)
			{
				int			fc_u_next = fc_state->pair_vu[fc_u_adj[fc_i]];

				if (fc_distance[fc_u_next] == HK_INFINITY)
				{
					fc_distance[fc_u_next] = 1 + fc_distance[fc_u];
					Assert(fc_qhead < fc_usize + 2);
					fc_queue[fc_qhead++] = fc_u_next;
				}
			}
		}
	}

	return (fc_distance[0] != HK_INFINITY);
}

/*
 * 执行H-K匹配的深度优先搜索步骤。
 * 如果成功，则返回true。
 */
static bool fc_hk_depth_search(BipartiteMatchState *fc_state, int fc_u)
{
	short	   *fc_distance = fc_state->distance;
	short	   *fc_pair_uv = fc_state->pair_uv;
	short	   *fc_pair_vu = fc_state->pair_vu;
	short	   *fc_u_adj = fc_state->adjacency[fc_u];
	int			fc_i = fc_u_adj ? fc_u_adj[0] : 0;
	short		fc_nextdist;

	if (fc_u == 0)
		return true;
	if (fc_distance[fc_u] == HK_INFINITY)
		return false;
	fc_nextdist = fc_distance[fc_u] + 1;

	check_stack_depth();

	for (; fc_i > 0; fc_i--)
	{
		int			fc_v = fc_u_adj[fc_i];

		if (fc_distance[fc_pair_vu[fc_v]] == fc_nextdist)
		{
			if (fc_hk_depth_search(fc_state, fc_pair_vu[fc_v]))
			{
				fc_pair_vu[fc_v] = fc_u;
				fc_pair_uv[fc_u] = fc_v;
				return true;
			}
		}
	}

	fc_distance[fc_u] = HK_INFINITY;
	return false;
}
